Termination w.r.t. Q proof of TRS/D3332.trs

Termination w.r.t. Q of the following Term Rewriting System could be proven:

Q restricted rewrite system:
The TRS R consists of the following rules:

sort(nil) → nil
sort(cons(x, y)) → insert(x, sort(y))
insert(x, nil) → cons(x, nil)
insert(x, cons(v, w)) → choose(x, cons(v, w), x, v)
choose(x, cons(v, w), y, 0) → cons(x, cons(v, w))
choose(x, cons(v, w), 0, s(z)) → cons(v, insert(x, w))
choose(x, cons(v, w), s(y), s(z)) → choose(x, cons(v, w), y, z)

Q is empty.

↳ QTRS

  ↳ Overlay + Local Confluence

Q restricted rewrite system:
The TRS R consists of the following rules:

sort(nil) → nil
sort(cons(x, y)) → insert(x, sort(y))
insert(x, nil) → cons(x, nil)
insert(x, cons(v, w)) → choose(x, cons(v, w), x, v)
choose(x, cons(v, w), y, 0) → cons(x, cons(v, w))
choose(x, cons(v, w), 0, s(z)) → cons(v, insert(x, w))
choose(x, cons(v, w), s(y), s(z)) → choose(x, cons(v, w), y, z)

Q is empty.

The TRS is overlay and locally confluent. By [15] we can switch to innermost.

↳ QTRS

  ↳ Overlay + Local Confluence

    ↳ QTRS

      ↳ DependencyPairsProof

Q restricted rewrite system:
The TRS R consists of the following rules:

sort(nil) → nil
sort(cons(x, y)) → insert(x, sort(y))
insert(x, nil) → cons(x, nil)
insert(x, cons(v, w)) → choose(x, cons(v, w), x, v)
choose(x, cons(v, w), y, 0) → cons(x, cons(v, w))
choose(x, cons(v, w), 0, s(z)) → cons(v, insert(x, w))
choose(x, cons(v, w), s(y), s(z)) → choose(x, cons(v, w), y, z)

The set Q consists of the following terms:

sort(nil)
sort(cons(x0, x1))
insert(x0, nil)
insert(x0, cons(x1, x2))
choose(x0, cons(x1, x2), x3, 0)
choose(x0, cons(x1, x2), 0, s(x3))
choose(x0, cons(x1, x2), s(x3), s(x4))

Using Dependency Pairs [1,13] we result in the following initial DP problem:
Q DP problem:
The TRS P consists of the following rules:

SORT(cons(x, y)) → INSERT(x, sort(y))
INSERT(x, cons(v, w)) → CHOOSE(x, cons(v, w), x, v)
CHOOSE(x, cons(v, w), s(y), s(z)) → CHOOSE(x, cons(v, w), y, z)
CHOOSE(x, cons(v, w), 0, s(z)) → INSERT(x, w)
SORT(cons(x, y)) → SORT(y)

The TRS R consists of the following rules:

sort(nil) → nil
sort(cons(x, y)) → insert(x, sort(y))
insert(x, nil) → cons(x, nil)
insert(x, cons(v, w)) → choose(x, cons(v, w), x, v)
choose(x, cons(v, w), y, 0) → cons(x, cons(v, w))
choose(x, cons(v, w), 0, s(z)) → cons(v, insert(x, w))
choose(x, cons(v, w), s(y), s(z)) → choose(x, cons(v, w), y, z)

The set Q consists of the following terms:

sort(nil)
sort(cons(x0, x1))
insert(x0, nil)
insert(x0, cons(x1, x2))
choose(x0, cons(x1, x2), x3, 0)
choose(x0, cons(x1, x2), 0, s(x3))
choose(x0, cons(x1, x2), s(x3), s(x4))

We have to consider all minimal (P,Q,R)-chains.

↳ QTRS

  ↳ Overlay + Local Confluence

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ EdgeDeletionProof

Q DP problem:
The TRS P consists of the following rules:

SORT(cons(x, y)) → INSERT(x, sort(y))
INSERT(x, cons(v, w)) → CHOOSE(x, cons(v, w), x, v)
CHOOSE(x, cons(v, w), s(y), s(z)) → CHOOSE(x, cons(v, w), y, z)
CHOOSE(x, cons(v, w), 0, s(z)) → INSERT(x, w)
SORT(cons(x, y)) → SORT(y)

The TRS R consists of the following rules:

sort(nil) → nil
sort(cons(x, y)) → insert(x, sort(y))
insert(x, nil) → cons(x, nil)
insert(x, cons(v, w)) → choose(x, cons(v, w), x, v)
choose(x, cons(v, w), y, 0) → cons(x, cons(v, w))
choose(x, cons(v, w), 0, s(z)) → cons(v, insert(x, w))
choose(x, cons(v, w), s(y), s(z)) → choose(x, cons(v, w), y, z)

The set Q consists of the following terms:

sort(nil)
sort(cons(x0, x1))
insert(x0, nil)
insert(x0, cons(x1, x2))
choose(x0, cons(x1, x2), x3, 0)
choose(x0, cons(x1, x2), 0, s(x3))
choose(x0, cons(x1, x2), s(x3), s(x4))

We have to consider all minimal (P,Q,R)-chains.
We deleted some edges using various graph approximations

↳ QTRS

  ↳ Overlay + Local Confluence

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ EdgeDeletionProof

            ↳ QDP

              ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

SORT(cons(x, y)) → INSERT(x, sort(y))
INSERT(x, cons(v, w)) → CHOOSE(x, cons(v, w), x, v)
CHOOSE(x, cons(v, w), s(y), s(z)) → CHOOSE(x, cons(v, w), y, z)
SORT(cons(x, y)) → SORT(y)
CHOOSE(x, cons(v, w), 0, s(z)) → INSERT(x, w)

The TRS R consists of the following rules:

sort(nil) → nil
sort(cons(x, y)) → insert(x, sort(y))
insert(x, nil) → cons(x, nil)
insert(x, cons(v, w)) → choose(x, cons(v, w), x, v)
choose(x, cons(v, w), y, 0) → cons(x, cons(v, w))
choose(x, cons(v, w), 0, s(z)) → cons(v, insert(x, w))
choose(x, cons(v, w), s(y), s(z)) → choose(x, cons(v, w), y, z)

The set Q consists of the following terms:

sort(nil)
sort(cons(x0, x1))
insert(x0, nil)
insert(x0, cons(x1, x2))
choose(x0, cons(x1, x2), x3, 0)
choose(x0, cons(x1, x2), 0, s(x3))
choose(x0, cons(x1, x2), s(x3), s(x4))

We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [13,14,18] contains 2 SCCs with 1 less node.

↳ QTRS

  ↳ Overlay + Local Confluence

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ EdgeDeletionProof

            ↳ QDP

              ↳ DependencyGraphProof

                ↳ AND

                  ↳ QDP

                    ↳ QDPOrderProof

                  ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

INSERT(x, cons(v, w)) → CHOOSE(x, cons(v, w), x, v)
CHOOSE(x, cons(v, w), s(y), s(z)) → CHOOSE(x, cons(v, w), y, z)
CHOOSE(x, cons(v, w), 0, s(z)) → INSERT(x, w)

The TRS R consists of the following rules:

sort(nil) → nil
sort(cons(x, y)) → insert(x, sort(y))
insert(x, nil) → cons(x, nil)
insert(x, cons(v, w)) → choose(x, cons(v, w), x, v)
choose(x, cons(v, w), y, 0) → cons(x, cons(v, w))
choose(x, cons(v, w), 0, s(z)) → cons(v, insert(x, w))
choose(x, cons(v, w), s(y), s(z)) → choose(x, cons(v, w), y, z)

The set Q consists of the following terms:

sort(nil)
sort(cons(x0, x1))
insert(x0, nil)
insert(x0, cons(x1, x2))
choose(x0, cons(x1, x2), x3, 0)
choose(x0, cons(x1, x2), 0, s(x3))
choose(x0, cons(x1, x2), s(x3), s(x4))

We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].

The following pairs can be oriented strictly and are deleted.

CHOOSE(x, cons(v, w), 0, s(z)) → INSERT(x, w)

The remaining pairs can at least be oriented weakly.

INSERT(x, cons(v, w)) → CHOOSE(x, cons(v, w), x, v)
CHOOSE(x, cons(v, w), s(y), s(z)) → CHOOSE(x, cons(v, w), y, z)

Used ordering: Combined order from the following AFS and order.
INSERT(x1, x2) = x2
cons(x1, x2) = cons(x2)
CHOOSE(x1, x2, x3, x4) = x2

Recursive Path Order [2].
Precedence:

trivial

The following usable rules [14] were oriented: none

↳ QTRS

  ↳ Overlay + Local Confluence

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ EdgeDeletionProof

            ↳ QDP

              ↳ DependencyGraphProof

                ↳ AND

                  ↳ QDP

                    ↳ QDPOrderProof

                      ↳ QDP

                        ↳ DependencyGraphProof

                  ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

INSERT(x, cons(v, w)) → CHOOSE(x, cons(v, w), x, v)
CHOOSE(x, cons(v, w), s(y), s(z)) → CHOOSE(x, cons(v, w), y, z)

The TRS R consists of the following rules:

sort(nil) → nil
sort(cons(x, y)) → insert(x, sort(y))
insert(x, nil) → cons(x, nil)
insert(x, cons(v, w)) → choose(x, cons(v, w), x, v)
choose(x, cons(v, w), y, 0) → cons(x, cons(v, w))
choose(x, cons(v, w), 0, s(z)) → cons(v, insert(x, w))
choose(x, cons(v, w), s(y), s(z)) → choose(x, cons(v, w), y, z)

The set Q consists of the following terms:

sort(nil)
sort(cons(x0, x1))
insert(x0, nil)
insert(x0, cons(x1, x2))
choose(x0, cons(x1, x2), x3, 0)
choose(x0, cons(x1, x2), 0, s(x3))
choose(x0, cons(x1, x2), s(x3), s(x4))

We have to consider all minimal (P,Q,R)-chains.
The approximation of the Dependency Graph [13,14,18] contains 1 SCC with 1 less node.

↳ QTRS

  ↳ Overlay + Local Confluence

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ EdgeDeletionProof

            ↳ QDP

              ↳ DependencyGraphProof

                ↳ AND

                  ↳ QDP

                    ↳ QDPOrderProof

                      ↳ QDP

                        ↳ DependencyGraphProof

                          ↳ QDP

                            ↳ QDPOrderProof

                  ↳ QDP

Q DP problem:
The TRS P consists of the following rules:

CHOOSE(x, cons(v, w), s(y), s(z)) → CHOOSE(x, cons(v, w), y, z)

The TRS R consists of the following rules:

sort(nil) → nil
sort(cons(x, y)) → insert(x, sort(y))
insert(x, nil) → cons(x, nil)
insert(x, cons(v, w)) → choose(x, cons(v, w), x, v)
choose(x, cons(v, w), y, 0) → cons(x, cons(v, w))
choose(x, cons(v, w), 0, s(z)) → cons(v, insert(x, w))
choose(x, cons(v, w), s(y), s(z)) → choose(x, cons(v, w), y, z)

The set Q consists of the following terms:

sort(nil)
sort(cons(x0, x1))
insert(x0, nil)
insert(x0, cons(x1, x2))
choose(x0, cons(x1, x2), x3, 0)
choose(x0, cons(x1, x2), 0, s(x3))
choose(x0, cons(x1, x2), s(x3), s(x4))

We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].

The following pairs can be oriented strictly and are deleted.

CHOOSE(x, cons(v, w), s(y), s(z)) → CHOOSE(x, cons(v, w), y, z)

The remaining pairs can at least be oriented weakly.
none
Used ordering: Combined order from the following AFS and order.
CHOOSE(x1, x2, x3, x4) = x4
s(x1) = s(x1)

Recursive Path Order [2].
Precedence:

trivial

The following usable rules [14] were oriented: none

↳ QTRS

  ↳ Overlay + Local Confluence

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ EdgeDeletionProof

            ↳ QDP

              ↳ DependencyGraphProof

                ↳ AND

                  ↳ QDP

                    ↳ QDPOrderProof

                      ↳ QDP

                        ↳ DependencyGraphProof

                          ↳ QDP

                            ↳ QDPOrderProof

                              ↳ QDP

                                ↳ PisEmptyProof

                  ↳ QDP

Q DP problem:
P is empty.
The TRS R consists of the following rules:

sort(nil) → nil
sort(cons(x, y)) → insert(x, sort(y))
insert(x, nil) → cons(x, nil)
insert(x, cons(v, w)) → choose(x, cons(v, w), x, v)
choose(x, cons(v, w), y, 0) → cons(x, cons(v, w))
choose(x, cons(v, w), 0, s(z)) → cons(v, insert(x, w))
choose(x, cons(v, w), s(y), s(z)) → choose(x, cons(v, w), y, z)

The set Q consists of the following terms:

sort(nil)
sort(cons(x0, x1))
insert(x0, nil)
insert(x0, cons(x1, x2))
choose(x0, cons(x1, x2), x3, 0)
choose(x0, cons(x1, x2), 0, s(x3))
choose(x0, cons(x1, x2), s(x3), s(x4))

We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.

↳ QTRS

  ↳ Overlay + Local Confluence

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ EdgeDeletionProof

            ↳ QDP

              ↳ DependencyGraphProof

                ↳ AND

                  ↳ QDP

                  ↳ QDP

                    ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

SORT(cons(x, y)) → SORT(y)

The TRS R consists of the following rules:

sort(nil) → nil
sort(cons(x, y)) → insert(x, sort(y))
insert(x, nil) → cons(x, nil)
insert(x, cons(v, w)) → choose(x, cons(v, w), x, v)
choose(x, cons(v, w), y, 0) → cons(x, cons(v, w))
choose(x, cons(v, w), 0, s(z)) → cons(v, insert(x, w))
choose(x, cons(v, w), s(y), s(z)) → choose(x, cons(v, w), y, z)

The set Q consists of the following terms:

sort(nil)
sort(cons(x0, x1))
insert(x0, nil)
insert(x0, cons(x1, x2))
choose(x0, cons(x1, x2), x3, 0)
choose(x0, cons(x1, x2), 0, s(x3))
choose(x0, cons(x1, x2), s(x3), s(x4))

We have to consider all minimal (P,Q,R)-chains.
We use the reduction pair processor [13].

The following pairs can be oriented strictly and are deleted.

SORT(cons(x, y)) → SORT(y)

The remaining pairs can at least be oriented weakly.
none
Used ordering: Combined order from the following AFS and order.
SORT(x1) = x1
cons(x1, x2) = cons(x2)

Recursive Path Order [2].
Precedence:

trivial

The following usable rules [14] were oriented: none

↳ QTRS

  ↳ Overlay + Local Confluence

    ↳ QTRS

      ↳ DependencyPairsProof

        ↳ QDP

          ↳ EdgeDeletionProof

            ↳ QDP

              ↳ DependencyGraphProof

                ↳ AND

                  ↳ QDP

                  ↳ QDP

                    ↳ QDPOrderProof

                      ↳ QDP

                        ↳ PisEmptyProof

Q DP problem:
P is empty.
The TRS R consists of the following rules:

sort(nil) → nil
sort(cons(x, y)) → insert(x, sort(y))
insert(x, nil) → cons(x, nil)
insert(x, cons(v, w)) → choose(x, cons(v, w), x, v)
choose(x, cons(v, w), y, 0) → cons(x, cons(v, w))
choose(x, cons(v, w), 0, s(z)) → cons(v, insert(x, w))
choose(x, cons(v, w), s(y), s(z)) → choose(x, cons(v, w), y, z)

The set Q consists of the following terms:

sort(nil)
sort(cons(x0, x1))
insert(x0, nil)
insert(x0, cons(x1, x2))
choose(x0, cons(x1, x2), x3, 0)
choose(x0, cons(x1, x2), 0, s(x3))
choose(x0, cons(x1, x2), s(x3), s(x4))

We have to consider all minimal (P,Q,R)-chains.
The TRS P is empty. Hence, there is no (P,Q,R) chain.